//给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。 
//
// 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 
//
// 注意: 
//假设字符串的长度不会超过 1010。 
//
// 示例 1: 
//
// 
//输入:
//"abccccdd"
//
//输出:
//7
//
//解释:
//我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
// 
// Related Topics 贪心 哈希表 字符串 
// 👍 347 👎 0

package com.cute.leetcode.editor.cn;
public class LongestPalindrome {
    public static void main(String[] args) {
        Solution solution = new LongestPalindrome().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * 想了一会儿就想明白了：
     *  就是统计字符串中字符出现的次数，偶数次的话直接加到结果中，有奇数次的话添加完偶数部分最终结果再+1就行了
     */
    public int longestPalindrome(String s) {
        int[] count = new int[58];
        for (char c : s.toCharArray()) count[c-'A']++;
        int res = 0;
        int ext = 0;
        for (int num : count){
            if (num%2!=0) {//出现了奇数次
                ext=1;//额外补一次
                res += (num -1);//添加偶数次的部分
            }else res += num;//偶数次直接加
        }
        return res + ext;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}